package com.hanxiaozhang.no10leetcode.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈二叉树锯齿形层次遍历〉
 * 实例:
 * 给定二叉树：[3,9,20,null,null,15,7]
 * .    3
 * .   / \
 * .  9  20
 * .    /  \
 * .   15   7
 * 将其Z字形级别的顺序遍历返回为:
 * [
 * [3],
 * [20,9],
 * [15,7]
 * ]
 * <p>
 * 思路：
 * 1. 增加方向指针，控制输出Z字型
 * 2. 增加记录每行第一个元素变量，创建每次集合
 *
 * @author hanxinghua
 * @create 2024/4/9
 * @since 1.0.0
 */
public class No103BinaryTreeZigzagLevelOrderTraversal {

    public static void main(String[] args) {

        TreeNode tree1 = new TreeNode(3);
        tree1.left = new TreeNode(9);
        tree1.right = new TreeNode(20);
        tree1.right.left = new TreeNode(15);
        tree1.right.right = new TreeNode(7);


        System.out.println(method1_step1(tree1));

        System.out.println(method1_step2(tree1));

    }

    /**
     * 方法1-步骤1：实现Z字形存储到一个集合
     *
     * @param root
     * @return
     */
    private static List<Integer> method1_step1(TreeNode root) {

        List<Integer> results = new ArrayList();
        if (root == null) {
            return results;
        }

        // 指针，0左 1 右
        int pointer = 1;

        LinkedList<TreeNode> helpQueue = new LinkedList();
        helpQueue.add(root);

        while (!helpQueue.isEmpty()) {
            TreeNode node = helpQueue.poll();
            results.add(node.val);

            if (pointer == 0) {
                if (node.left != null) {
                    helpQueue.add(node.left);
                }
                if (node.right != null) {
                    helpQueue.add(node.right);
                }
                pointer = 1;
            } else {
                if (node.right != null) {
                    helpQueue.add(node.right);
                }
                if (node.left != null) {
                    helpQueue.add(node.left);
                }
                pointer = 0;
            }
        }
        return results;
    }

    /**
     * 方法1-步骤2：实现Z字形存储到多个集合中
     *
     * @param root
     * @return
     */
    private static List<List<Integer>> method1_step2(TreeNode root) {

        List<List<Integer>> results = new ArrayList();
        if (root == null) {
            return results;
        }

        // 左方向指针: true 左 false 右  默认第一次 是右方向指针
        boolean leftPointer = false;
        // 每层第一个元素
        TreeNode layerFirst = root;

        LinkedList<TreeNode> helpQueue = new LinkedList();
        helpQueue.add(root);

        List<Integer> result = null;

        while (!helpQueue.isEmpty()) {
            TreeNode node = helpQueue.poll();

            if (node == layerFirst) {
                result = new ArrayList<>();
                results.add(result);
            }

            if (leftPointer) {
                if (node.left != null) {
                    helpQueue.add(node.left);
                    layerFirst = node.left;
                }
                if (node.right != null) {
                    helpQueue.add(node.right);
                    if (node.left == null) {
                        layerFirst = node.right;
                    }
                }
                leftPointer = false;
            } else {
                if (node.right != null) {
                    helpQueue.add(node.right);
                    layerFirst = node.right;
                }
                if (node.left != null) {
                    helpQueue.add(node.left);
                    if (node.right == null) {
                        layerFirst = node.left;
                    }
                }
                leftPointer = true;
            }
            result.add(node.val);

        }
        return results;
    }


}
